#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>

using namespace std;

// 考生结构体
struct Student {
    string id;
    int score;
};

// 按分数非升序，准考证号字典序递增排序
bool cmp1(const Student& a, const Student& b) {
    if (a.score != b.score) {
        return a.score > b.score;
    }
    return a.id < b.id;
}

// 按人数非递增，考场编号递增排序
bool cmp2(const pair<int, int>& a, const pair<int, int>& b) {
    if (a.second != b.second) {
        return a.second > b.second;
    }
    return a.first < b.first;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<Student> students(N);
    for (int i = 0; i < N; ++i) {
        cin >> students[i].id >> students[i].score;
    }

    for (int i = 1; i <= M; ++i) {
        int type;
        string command;
        cin >> type >> command;
        cout << "Case " << i << ": " << type << " " << command << endl;

        if (type == 1) {
            vector<Student> res;
            for (const auto& s : students) {
                // 使用 substr 提取级别
                if (s.id.substr(0, 1) == command) { 
                    res.push_back(s);
                }
            }
            sort(res.begin(), res.end(), cmp1);
            if (res.empty()) {
                cout << "NA" << endl;
            } else {
                for (const auto& s : res) {
                    cout << s.id << " " << s.score << endl;
                }
            }
        } else if (type == 2) {
            int count = 0, totalScore = 0;
            for (const auto& s : students) {
                // 使用 substr 提取考场编号
                if (s.id.substr(1, 3) == command) { 
                    ++count;
                    totalScore += s.score;
                }
            }
            if (count == 0) {
                cout << "NA" << endl;
            } else {
                cout << count << " " << totalScore << endl;
            }
        } else if (type == 3) {
            unordered_map<int, int> mp;
            for (const auto& s : students) {
                // 使用 substr 提取考试日期
                if (s.id.substr(4, 6) == command) { 
                    // 使用 substr 提取考场编号
                    int room = stoi(s.id.substr(1, 3)); 
                    ++mp[room];
                }
            }
            vector<pair<int, int>> res(mp.begin(), mp.end());
            sort(res.begin(), res.end(), cmp2);
            if (res.empty()) {
                cout << "NA" << endl;
            } else {
                for (const auto& p : res) {
                    cout << p.first << " " << p.second << endl;
                }
            }
        }
    }

    return 0;
}    